The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for addressing cross-allocated blocks in a file system.
A file system is a means to organize data expected to be retained after a program terminates by storing, retrieving, and updating data, as well as managing available space on device(s) which comprises the file system. A file system organizes data in an efficient manner and is tuned to characteristics specific to the device or disk which comprises the file system. Some file systems provide mechanisms to control access to the data and metadata. Ensuring reliability is a major responsibility of a file system.
Some current disks support many different file systems providing flexibility so that many operating systems may be supported, file systems such as: ext, ext2, xia, minix, umsdos, msdos, vat, proc, smb, ncp, iso9660, sysv, hpfs, affs, and ufs, and no doubt, over time more will be added. Each of the separate file systems may be combined into a single hierarchical tree structure that represents the file system as one whole single entity. That is, as each new files system is mounted on a disk, the disk adds the new file system into this single file system tree.
When a disk is initialized, the disk has a partition structure imposed that divides the physical disk into a number of logical partitions. Each partition may hold a single file system. File systems organize files into logical hierarchical structures with directories, soft links, and so on, held in blocks on physical devices. Devices that can contain file systems are known as block devices. These block devices are, thus, simply linear collections of blocks that exist without regard to the underlying physical disk's geometry. It is the task of a block device driver associated with each block to map a request to read a particular block of its disk into terms meaningful to its disk; the particular track, sector, and cylinder of its hard disk where the block is kept.
Thus, the files in a file system are collections of data. A file system not only holds the data that is contained within the files of the file system but also the structure of the file system. Thus, a layout of a file system may be illustrated as the file system occupying a series of blocks in a block structured device. So far as each file system is concerned, block devices are just a series of blocks that can be read and written. The file system divides the logical partition that it occupies into block groups. Each block group duplicates information critical to the integrity of the file system as well as holding real files and directories as blocks of information and data.
In a file system, an inode is the basic building block. Every file and directory in the file system is described by one and only one inode. If a block is referred to across multiple inodes or multiple times within the same inode, these are called cross-allocated blocks or duplicate blocks. Such allocations are quite dangerous as these cross-allocated blocks or duplicate blocks point to data corruption and at times having an inode(s) referring a block that is already freed—caused by one of the other inodes that was cross referring the block being freed.